package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         28,
		Discription: "KMP",
		Level:       3,
		Labels: map[string]int{
			"字符串":   1,
			"动态规划":  1,
			"双指针滑动": 1,
		},
	})
}

// KMP 通过needle的头尾字符串部分相等的特性(不是回文)减少不必要的匹配
//  @param haystack
//  @param needle
//  @return int
func KMP(haystack string, needle string) int {
	next := make([]int, len(needle))
	next[0] = 0
	//next[i]的定义：next[:i+1]中头尾相等的字符个数，方便needle的回退
	//比如needle[j]匹配不上了，那就说明到j-1还是能匹配上的，那就把j移到开头最后一个能匹配的元素的后一位，haystack的指针不动接着匹配，直到j=0还是匹配不上再移动i
	//j：左指针
	//i：右指针
	for i, j := 1, 0; i < len(needle); i++ {
		//不相等回退j，直到回退到最开始的字符
		for j > 0 && needle[j] != needle[i] {
			j = next[j-1]
		}

		//到这里有两种情况
		//needle[:j+1]和needle[i-j:i+1]是一样的，所以s[:i+1]头尾相等的字符串有j+1个，next[i]=j+1
		//j=0,且头尾不相等，直接next[i]=0
		if needle[j] == needle[i] {
			j++
		}

		//此时j要么等于0，要么needle[j] == needle[i]
		//两种情况下，j都是头尾相等的字符个数
		next[i] = j
	}

	//i：haystack的指针
	//j：needle的指针
	//注意i++不由大循环控制
	for i, j := 0, 0; i < len(haystack); {
		//一直匹配一直加，只要不越界
		for i < len(haystack) && j < len(needle) && haystack[i] == needle[j] {
			i++
			j++
		}

		//匹配成功
		if j == len(needle) {
			return i - len(needle)
		}

		//j==0表示needle没有可回退的了，haystack必须挪到下一位
		if j == 0 {
			i++
		} else {
			//回退needle
			j = next[j-1]
		}
	}

	return -1
}
